#include <vector>

using namespace std;

// 思路： 二分查找 找到目标值的第一个位置和最后一个位置
// 第一个位置： 找到目标值后继续向左查找
// 最后一个位置： 找到目标值后继续向右查找
class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        int left = binSerch(nums, target, true);
        int right = binSerch(nums, target, false);
        return {left, right};
    }
    int binSerch(vector<int> &nums, int target, bool isLeft)
    {
        int left = 0;
        int right = nums.size() - 1;
        int index = -1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (target == nums[mid])
            {
                index = mid; // 记录当前找到的目标值位置
                // 继续向左或向右查找
                if (isLeft)
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else if (target > nums[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return index;
    }
};